package alogrithm;

import java.util.Stack;

/**
 * @author lbw
 * @version 1.0
 * @date 2021/9/12 11:50
 */
public class Pair69 {

    public static void main(String[] args) {

    }

    public String Paired69(String S) {
        // write code here
        StringBuilder sb = new StringBuilder();
        Stack<Character> stk = new Stack<>();
        for (char ch : S.toCharArray()) {
            if (ch == '6') {
                stk.push(ch);
            } else {
                if (!stk.isEmpty()) {
                    stk.pop();
                } else {
                    sb.insert(0, "6");
                }
            }
            sb.append(ch);
        }
        while (!stk.isEmpty()) {
            stk.pop();
            sb.append("9");
        }
        return sb.toString();
    }
}
